Computing Functional Dependencies with Pattern Structures
Identifieur interne : 001904 ( Main/Exploration ); précédent : 001903; suivant : 001905Computing Functional Dependencies with Pattern Structures
Auteurs : Jaume Baixeries [Espagne] ; Mehdi Kaytoue [France] ; Amedeo Napoli [France]Source :
English descriptors
Abstract
The treatment of many-valued data with FCA has been achieved by means of scaling. This method has some drawbacks, since the size of the resulting formal contexts depends usually on the number of di erent values that are present in a table, which can be very large. Pattern structures have been proved to deal with many-valued data, offering a viable and sound alternative to scaling in order to represent and analyze sets of many-valued data with FCA. Functional dependencies have already been dealt with FCA using the binarization of a table, that is, creating a formal context out of a set of data. Unfortunately, although this method is standard and simple, it has an important drawback, which is the fact that the resulting context is quadratic in number of objects w.r.t. the original set of data. In this paper, we examine how we can extract the functional dependencies that hold in a set of data using pattern structures. This allows to build an equivalent concept lattice avoiding the step of binarization, and thus comes with better concept representation and computation.
Url:
Affiliations:
- Espagne, France
- Auvergne-Rhône-Alpes, Grand Est, Lorraine (région), Rhône-Alpes
- Lyon, Metz, Nancy
- Université Claude Bernard Lyon 1, Université de Lorraine, Université de Lyon
Links toward previous steps (curation, corpus...)
- to stream Hal, to step Corpus: 001769
- to stream Hal, to step Curation: 001769
- to stream Hal, to step Checkpoint: 001520
- to stream Main, to step Merge: 001933
- to stream Main, to step Curation: 001904
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Computing Functional Dependencies with Pattern Structures</title><author><name sortKey="Baixeries, Jaume" sort="Baixeries, Jaume" uniqKey="Baixeries J" first="Jaume" last="Baixeries">Jaume Baixeries</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-74848" status="VALID"><orgName>Llenguatges i Sistemes Informàtics</orgName><orgName type="acronym">LSI</orgName><desc><address><addrLine>Universitat Politécnica de Catalunya FIB / FME C/ Pau Gargallo 5, E-Barcelona 08028</addrLine><country key="ES"></country></address><ref type="url">http://www.lsi.upc.edu/</ref></desc><listRelation><relation active="#struct-85878" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-85878" type="direct"><org type="institution" xml:id="struct-85878" status="VALID"><orgName>Universitat Politècnica de Catalunya [Barcelona]</orgName><orgName type="acronym">UPC</orgName><desc><address><addrLine>Universitat Politècnica de Catalunya C. Jordi Girona, 31. 08034 Barcelona</addrLine><country key="ES"></country></address><ref type="url">http://www.upc.edu/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>Espagne</country></affiliation></author><author><name sortKey="Kaytoue, Mehdi" sort="Kaytoue, Mehdi" uniqKey="Kaytoue M" first="Mehdi" last="Kaytoue">Mehdi Kaytoue</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-2003" status="VALID"><orgName>Laboratoire d'InfoRmatique en Image et Systèmes d'information</orgName><orgName type="acronym">LIRIS</orgName><desc><address><addrLine>Bâtiment Blaise Pascal - 20, avenue Albert Einstein - 69621 Villeurbanne cedex</addrLine><country key="FR"></country></address><ref type="url">http://liris.cnrs.fr/</ref></desc><listRelation><relation active="#struct-33804" type="direct"></relation><relation active="#struct-126765" type="direct"></relation><relation active="#struct-194495" type="direct"></relation><relation name="- LYON" active="#struct-301232" type="direct"></relation><relation name="UMR5205" active="#struct-441569" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-33804" type="direct"><org type="institution" xml:id="struct-33804" status="VALID"><orgName>Université Lumière - Lyon 2</orgName><orgName type="acronym">UL2</orgName><desc><address><addrLine>86, rue Pasteur - 69007 Lyon</addrLine><country key="FR"></country></address><ref type="url">http://www.univ-lyon2.fr</ref></desc></org></tutelle><tutelle active="#struct-126765" type="direct"><org type="institution" xml:id="struct-126765" status="VALID"><orgName>École Centrale de Lyon</orgName><orgName type="acronym">ECL</orgName><desc><address><addrLine>36 avenue Guy de Collongue - 69134 Ecully cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.ec-lyon.fr</ref></desc></org></tutelle><tutelle active="#struct-194495" type="direct"><org type="institution" xml:id="struct-194495" status="VALID"><orgName>Université Claude Bernard Lyon 1</orgName><orgName type="acronym">UCBL</orgName><desc><address><addrLine>43, boulevard du 11 novembre 1918, 69622 Villeurbanne cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.univ-lyon1.fr/</ref></desc></org></tutelle><tutelle name="- LYON" active="#struct-301232" type="direct"><org type="institution" xml:id="struct-301232" status="VALID"><orgName>Institut National des Sciences Appliquées</orgName><orgName type="acronym">INSA</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle name="UMR5205" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="IdRef">02636817X</idno><idno type="ISNI">0000000122597504</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Lyon</settlement><region type="region" nuts="2">Auvergne-Rhône-Alpes</region><region type="old region" nuts="2">Rhône-Alpes</region></placeName><orgName type="university">Université Claude Bernard Lyon 1</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lyon</orgName></affiliation></author><author><name sortKey="Napoli, Amedeo" sort="Napoli, Amedeo" uniqKey="Napoli A" first="Amedeo" last="Napoli">Amedeo Napoli</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-205125" status="VALID"><idno type="RNSR">200818291B</idno><orgName>Knowledge representation, reasonning</orgName><orgName type="acronym">ORPAILLEUR</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.inria.fr/equipes/orpailleur</ref></desc><listRelation><relation active="#struct-129671" type="direct"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-423086" type="direct"></relation><relation active="#struct-206040" type="indirect"></relation><relation active="#struct-413289" type="indirect"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation></listRelation><tutelles><tutelle active="#struct-129671" type="direct"><org type="laboratory" xml:id="struct-129671" status="VALID"><idno type="RNSR">198618246Y</idno><orgName>INRIA Nancy - Grand Est</orgName><desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/nancy</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-423086" type="direct"><org type="department" xml:id="struct-423086" status="VALID"><orgName>Department of Natural Language Processing & Knowledge Discovery</orgName><orgName type="acronym">LORIA - NLPKD</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.loria.fr/la-recherche-en/departements/Knowledge-and-Language-Management</ref></desc><listRelation><relation active="#struct-206040" type="direct"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-413289" type="indirect"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation></listRelation></org></tutelle><tutelle active="#struct-206040" type="indirect"><org type="laboratory" xml:id="struct-206040" status="VALID"><idno type="IdRef">067077927</idno><idno type="RNSR">198912571S</idno><idno type="IdUnivLorraine">[UL]RSI--</idno><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName><orgName type="acronym">LORIA</orgName><date type="start">2012-01-01</date><desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.loria.fr</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-413289" type="direct"></relation><relation name="UMR7503" active="#struct-441569" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-413289" type="indirect"><org type="institution" xml:id="struct-413289" status="VALID"><idno type="IdRef">157040569</idno><idno type="IdUnivLorraine">[UL]100--</idno><orgName>Université de Lorraine</orgName><orgName type="acronym">UL</orgName><date type="start">2012-01-01</date><desc><address><addrLine>34 cours Léopold - CS 25233 - 54052 Nancy cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.univ-lorraine.fr/</ref></desc></org></tutelle><tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="IdRef">02636817X</idno><idno type="ISNI">0000000122597504</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Nancy</settlement><settlement type="city">Metz</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Université de Lorraine</orgName></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">HAL</idno><idno type="RBID">Hal:hal-00763748</idno><idno type="halId">hal-00763748</idno><idno type="halUri">https://hal.inria.fr/hal-00763748</idno><idno type="url">https://hal.inria.fr/hal-00763748</idno><date when="2012-10-11">2012-10-11</date><idno type="wicri:Area/Hal/Corpus">001769</idno><idno type="wicri:Area/Hal/Curation">001769</idno><idno type="wicri:Area/Hal/Checkpoint">001520</idno><idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">001520</idno><idno type="wicri:Area/Main/Merge">001933</idno><idno type="wicri:Area/Main/Curation">001904</idno><idno type="wicri:Area/Main/Exploration">001904</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">Computing Functional Dependencies with Pattern Structures</title><author><name sortKey="Baixeries, Jaume" sort="Baixeries, Jaume" uniqKey="Baixeries J" first="Jaume" last="Baixeries">Jaume Baixeries</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-74848" status="VALID"><orgName>Llenguatges i Sistemes Informàtics</orgName><orgName type="acronym">LSI</orgName><desc><address><addrLine>Universitat Politécnica de Catalunya FIB / FME C/ Pau Gargallo 5, E-Barcelona 08028</addrLine><country key="ES"></country></address><ref type="url">http://www.lsi.upc.edu/</ref></desc><listRelation><relation active="#struct-85878" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-85878" type="direct"><org type="institution" xml:id="struct-85878" status="VALID"><orgName>Universitat Politècnica de Catalunya [Barcelona]</orgName><orgName type="acronym">UPC</orgName><desc><address><addrLine>Universitat Politècnica de Catalunya C. Jordi Girona, 31. 08034 Barcelona</addrLine><country key="ES"></country></address><ref type="url">http://www.upc.edu/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>Espagne</country></affiliation></author><author><name sortKey="Kaytoue, Mehdi" sort="Kaytoue, Mehdi" uniqKey="Kaytoue M" first="Mehdi" last="Kaytoue">Mehdi Kaytoue</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-2003" status="VALID"><orgName>Laboratoire d'InfoRmatique en Image et Systèmes d'information</orgName><orgName type="acronym">LIRIS</orgName><desc><address><addrLine>Bâtiment Blaise Pascal - 20, avenue Albert Einstein - 69621 Villeurbanne cedex</addrLine><country key="FR"></country></address><ref type="url">http://liris.cnrs.fr/</ref></desc><listRelation><relation active="#struct-33804" type="direct"></relation><relation active="#struct-126765" type="direct"></relation><relation active="#struct-194495" type="direct"></relation><relation name="- LYON" active="#struct-301232" type="direct"></relation><relation name="UMR5205" active="#struct-441569" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-33804" type="direct"><org type="institution" xml:id="struct-33804" status="VALID"><orgName>Université Lumière - Lyon 2</orgName><orgName type="acronym">UL2</orgName><desc><address><addrLine>86, rue Pasteur - 69007 Lyon</addrLine><country key="FR"></country></address><ref type="url">http://www.univ-lyon2.fr</ref></desc></org></tutelle><tutelle active="#struct-126765" type="direct"><org type="institution" xml:id="struct-126765" status="VALID"><orgName>École Centrale de Lyon</orgName><orgName type="acronym">ECL</orgName><desc><address><addrLine>36 avenue Guy de Collongue - 69134 Ecully cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.ec-lyon.fr</ref></desc></org></tutelle><tutelle active="#struct-194495" type="direct"><org type="institution" xml:id="struct-194495" status="VALID"><orgName>Université Claude Bernard Lyon 1</orgName><orgName type="acronym">UCBL</orgName><desc><address><addrLine>43, boulevard du 11 novembre 1918, 69622 Villeurbanne cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.univ-lyon1.fr/</ref></desc></org></tutelle><tutelle name="- LYON" active="#struct-301232" type="direct"><org type="institution" xml:id="struct-301232" status="VALID"><orgName>Institut National des Sciences Appliquées</orgName><orgName type="acronym">INSA</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle name="UMR5205" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="IdRef">02636817X</idno><idno type="ISNI">0000000122597504</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Lyon</settlement><region type="region" nuts="2">Auvergne-Rhône-Alpes</region><region type="old region" nuts="2">Rhône-Alpes</region></placeName><orgName type="university">Université Claude Bernard Lyon 1</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lyon</orgName></affiliation></author><author><name sortKey="Napoli, Amedeo" sort="Napoli, Amedeo" uniqKey="Napoli A" first="Amedeo" last="Napoli">Amedeo Napoli</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-205125" status="VALID"><idno type="RNSR">200818291B</idno><orgName>Knowledge representation, reasonning</orgName><orgName type="acronym">ORPAILLEUR</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.inria.fr/equipes/orpailleur</ref></desc><listRelation><relation active="#struct-129671" type="direct"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-423086" type="direct"></relation><relation active="#struct-206040" type="indirect"></relation><relation active="#struct-413289" type="indirect"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation></listRelation><tutelles><tutelle active="#struct-129671" type="direct"><org type="laboratory" xml:id="struct-129671" status="VALID"><idno type="RNSR">198618246Y</idno><orgName>INRIA Nancy - Grand Est</orgName><desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/nancy</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-423086" type="direct"><org type="department" xml:id="struct-423086" status="VALID"><orgName>Department of Natural Language Processing & Knowledge Discovery</orgName><orgName type="acronym">LORIA - NLPKD</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.loria.fr/la-recherche-en/departements/Knowledge-and-Language-Management</ref></desc><listRelation><relation active="#struct-206040" type="direct"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-413289" type="indirect"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation></listRelation></org></tutelle><tutelle active="#struct-206040" type="indirect"><org type="laboratory" xml:id="struct-206040" status="VALID"><idno type="IdRef">067077927</idno><idno type="RNSR">198912571S</idno><idno type="IdUnivLorraine">[UL]RSI--</idno><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName><orgName type="acronym">LORIA</orgName><date type="start">2012-01-01</date><desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.loria.fr</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-413289" type="direct"></relation><relation name="UMR7503" active="#struct-441569" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-413289" type="indirect"><org type="institution" xml:id="struct-413289" status="VALID"><idno type="IdRef">157040569</idno><idno type="IdUnivLorraine">[UL]100--</idno><orgName>Université de Lorraine</orgName><orgName type="acronym">UL</orgName><date type="start">2012-01-01</date><desc><address><addrLine>34 cours Léopold - CS 25233 - 54052 Nancy cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.univ-lorraine.fr/</ref></desc></org></tutelle><tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="IdRef">02636817X</idno><idno type="ISNI">0000000122597504</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Nancy</settlement><settlement type="city">Metz</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Université de Lorraine</orgName></affiliation></author></analytic></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="mix" xml:lang="en"><term>data dependencies</term><term>formal concept analysis</term><term>pattern structures</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">The treatment of many-valued data with FCA has been achieved by means of scaling. This method has some drawbacks, since the size of the resulting formal contexts depends usually on the number of di erent values that are present in a table, which can be very large. Pattern structures have been proved to deal with many-valued data, offering a viable and sound alternative to scaling in order to represent and analyze sets of many-valued data with FCA. Functional dependencies have already been dealt with FCA using the binarization of a table, that is, creating a formal context out of a set of data. Unfortunately, although this method is standard and simple, it has an important drawback, which is the fact that the resulting context is quadratic in number of objects w.r.t. the original set of data. In this paper, we examine how we can extract the functional dependencies that hold in a set of data using pattern structures. This allows to build an equivalent concept lattice avoiding the step of binarization, and thus comes with better concept representation and computation.</div></front></TEI><affiliations><list><country><li>Espagne</li><li>France</li></country><region><li>Auvergne-Rhône-Alpes</li><li>Grand Est</li><li>Lorraine (région)</li><li>Rhône-Alpes</li></region><settlement><li>Lyon</li><li>Metz</li><li>Nancy</li></settlement><orgName><li>Université Claude Bernard Lyon 1</li><li>Université de Lorraine</li><li>Université de Lyon</li></orgName></list><tree><country name="Espagne"><noRegion><name sortKey="Baixeries, Jaume" sort="Baixeries, Jaume" uniqKey="Baixeries J" first="Jaume" last="Baixeries">Jaume Baixeries</name></noRegion></country><country name="France"><region name="Auvergne-Rhône-Alpes"><name sortKey="Kaytoue, Mehdi" sort="Kaytoue, Mehdi" uniqKey="Kaytoue M" first="Mehdi" last="Kaytoue">Mehdi Kaytoue</name></region><name sortKey="Napoli, Amedeo" sort="Napoli, Amedeo" uniqKey="Napoli A" first="Amedeo" last="Napoli">Amedeo Napoli</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001904 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 001904 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Exploration
|type= RBID
|clé= Hal:hal-00763748
|texte= Computing Functional Dependencies with Pattern Structures
}}
| This area was generated with Dilib version V0.6.33. |  |